//
//  PermuteUnique.swift
//  LeetCodeDemo
//
//  Created by Yangdongwu on 2020/12/20.
//

import Foundation

class PermuteUnique {
    
    var res = [[Int]]()
    var temp = [Int]()
    var visited = [Bool]()
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        visited = [Bool](repeating: false, count: nums.count)
        backstrack(nums.sorted(by: <), 0)
        return res
    }
    
    func backstrack(_ nums: [Int], _ index: Int) {
        if temp.count == nums.count {
            res.append(temp)
            return
        }
        for i in 0..<nums.count {
            if visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue
            }
            temp.append(nums[i])
            visited[i] = true
            backstrack(nums, index + 1)
            visited[i] = false
            temp.remove(at: index)
        }
    }
}
